202，查找-二分法查找

二分法查找适用于大的数据，但前提条件是数据必须是有序的，他的原理是先和中间的比较，如果等于就直接返回，如果小于就在前半部分继续使用二分法进行查找，如果大于则在后半部分继续使用二分法进行查找……我们来看下代码

 1public static int binarySearch(int[] array, int value) {
 2    int low = 0;
 3    int high = array.length - 1;
 4    while (low <= high) {
 5        int middle = low + ((high - low) >> 1);
 6        //  int middle = (low + high) >> 1;
 7        if (value == array[middle])
 8            return middle;
 9        if (value > array[middle])
10            low = middle + 1;
11        else
12            high = middle - 1;
13    }
14    return -1;
15}

上面的求middle的方法最好不要使用注释的部分，因为当数组比较大的时候，low+high可能会溢出。上面是通过while循环的方式，我们也可以不使用循环，使用递归的方式来求，看下代码

 1public static int binarySearch(int[] array, int value) {
 2    int low = 0;
 3    int high = array.length - 1;
 4    return searchmy(array, low, high, value);
 5}
 6
 7private static int searchmy(int array[], int low, int high, int value) {
 8    if (low > high)
 9        return -1;
10    int mid = low + ((high - low) >> 1);
11    if (value == array[mid])
12        return mid;
13    if (value < array[mid])
14        return searchmy(array, low, mid - 1, value);
15    return searchmy(array, mid + 1, high, value);
16}